package MyGraph;

public class DFS {
    // 深度优先 递归算法 遍历图

    // 辨识数组  防止重复遍历结点造成死结
    int[] visited;
    public void DFSTraverser(IGraph g) throws Exception{
        visited = new int[g.getVNum()];
        for(int i =0; i<g.getVNum(); i++){
            if(visited[i]==0){
                DFS(g, i);
            }
        }
    }

    public void DFS(IGraph g, int i)throws Exception{
        // g : 图
        // i : 第几个顶点

        // 首先让辨识数组置为1证明其完成过遍历
        visited[i] = 1;
        // 输出顶点信息
        System.out.println(g.getVex(i).toString()+" ");

        // 对于为访问的顶点开始遍历
        // firstAdj(i) 下一个邻接点
        // nextAdj(i, u)  相对于u的下一个邻接点
        // 以上就是遍历的核心
        for(int u=g.firstAdj(i); u>=0; u=g.nextAdj(i, u)){
            if(visited[u]==0){
                DFS(g, u);
            }
        }
    }


}
